package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-04 14:37
 */
public class BuyAndSellSocketWithPeriod {
    /**股票问题的关键在于列出所有的状态
     * 五部曲：dp[i][0]代表当前持有股票的最大利润 dp[i][1]代表保持卖出股票（代表股票不是今天卖出，也不是昨天卖出（之前的卖出））dp[i][3]
     * 代表在冷冻期内，表示昨天卖出的股票
     * 递推公式
     * dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
     *             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
     *             dp[i][2]=dp[i-1][0]+prices[i];
     *             dp[i][3]=dp[i-1][2];
     *             遍历顺序：从前往后遍历
     *             初始化：dp[0][0]=-prices[i] dp[0][1]=0(两天前肯定没有出售股票)dp[0][2]=0(当天买入和卖出)dp[0][3]=0 前一天没有出售股票
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        //创建数组
        int[][]dp=new int[prices.length][4];
        //进行初始化
        dp[0][0]=-prices[0];//0代表持有股票
        dp[0][1]=0;//1代表保持卖出股票
        dp[0][2]=0;//2表示卖出股票
        dp[0][3]=0;//3表示在冷冻期内
        //进行遍历循环
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        //返回最后卖出股票中的最大值
        return Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
    }
}
